#include <iostream>
#include "BinaryTree.h"
#include <climits> 
#define NEG_INF INT_MIN
using namespace std;

int main()
{
    BinarySearchTree<int> bst;
    int NUMS = 400000;
    int GAP  =   3711;
    int i;

    cout << "1_Checking BinarySearchTree... (no more output means success)" << endl;

    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        bst.insert( i );

    for( i = 1; i < NUMS; i+= 2 )
        bst.remove( i );

    if( NUMS < 40 )
        bst.printTree( );
    if( bst.findMin( ) != 2 || bst.findMax( ) != NUMS - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS; i+=2 )
        if( !bst.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i+=2 )
    {
        if( bst.contains( i ) )
            cout << "Find error2!" << endl;
    }

    BinarySearchTree<int> bst2;
    bst2 = bst;

    for( i = 2; i < NUMS; i+=2 )
        if( !bst2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i+=2 )
    {
        if( bst2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "Finished BinarySearchTree testing" << endl;
    
    AvlTree<int> avlt;
    NUMS = 20000;
    GAP  =   37;

    cout << "2_Checking AvlTree... (no more output means success)" << endl;

    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        avlt.insert( i );
    avlt.remove( 0 );
    for( i = 1; i < NUMS; i += 2 )
        avlt.remove( i );

    if( NUMS < 40 )
        avlt.printTree( );
    if( avlt.findMin( ) != 2 || avlt.findMax( ) != NUMS - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS; i += 2 )
        if( !avlt.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i += 2 )
    {
        if( avlt.contains( i )  )
            cout << "Find error2!" << endl;
    }

    AvlTree<int> avlt2;
    avlt2 = avlt;

    for( i = 2; i < NUMS; i += 2 )
        if( !avlt2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i += 2 )
    {
        if( avlt2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "Finished AvlTree testing" << endl;

    RedBlackTree<int> rbt(NEG_INF);
    NUMS = 400000;
    GAP  =   37;

    cout << "3_Checking RedBlackTree (no more output means success)" << endl;

    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        rbt.insert( i );

    if( NUMS < 40 )
        rbt.printTree( );
    if( rbt.findMin( ) != 1 || rbt.findMax( ) != NUMS - 1 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 1; i < NUMS; ++i )
        if( !rbt.contains( i ) )
            cout << "Find error1!" << endl;
    if( rbt.contains( 0 ) )
        cout << "Oops!" << endl;

    
    RedBlackTree<int> rbt2{ NEG_INF };
    rbt2 = rbt;

    for( i = 1; i < NUMS; ++i )
        if( !rbt2.contains( i ) )
            cout << "Find error1!" << endl;
    if( rbt2.contains( 0 ) )
        cout << "Oops!" << endl;

    cout << "Finished RedBlackTree testing" << endl;

    RedBlackTree<int> rbt3{ NEG_INF };
    rbt3 = rbt;

    cout << "4_Checking RedBlackTree delete operation... (no more output means success)" << endl;

    // Inserting elements into the RedBlackTree
    for(i = GAP; i != 0; i = (i + GAP) % NUMS)
        rbt.insert(i);

    // Deleting elements from the RedBlackTree
    for(i = GAP; i != 0; i = (i + GAP) % NUMS)
        rbt.remove(i);

    // Checking if the deleted elements are still present
    for(i = GAP; i != 0; i = (i + GAP) % NUMS)
        if(rbt.contains(i))
            cout << "Delete error!" << endl;

    cout << "Finished RedBlackTree delete operation testing" << endl;

    
    SplayTree<int> st;
    NUMS = 30000;
    GAP  =   37;

    cout << "5_Checking SplayTree (no more output means success)" << endl;

    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        st.insert( i );

    for( i = 1; i < NUMS; i+= 2 )
        st.remove( i );

    if( NUMS < 40 )
        st.printTree( );
    if( st.findMin( ) != 2 || st.findMax( ) != NUMS - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 2; i < NUMS; i+=2 )
        if( !st.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i+=2 )
    {
        if( st.contains( i ) )
            cout << "Find error2!" << endl;
    }

    SplayTree<int> st2;
    st2 = st;

    for( i = 2; i < NUMS; i+=2 )
        if( !st2.contains( i ) )
            cout << "Find error1!" << endl;

    for( i = 1; i < NUMS; i+=2 )
    {
        if( st2.contains( i ) )
            cout << "Find error2!" << endl;
    }

    cout << "Finished SplayTree testing" << endl;
    return 0;
}